// 数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

// 示例 1：
// 输入：[1,2,5,9,5,9,5,5,5]
// 输出：5
//  
// 示例 2：
// 输入：[3,2]
// 输出：-1
//  
// 示例 3：
// 输入：[2,2,1,1,1,2,2]
// 输出：2
//  
// 说明：
// 你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/find-majority-element-lcci
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// ①
var majorityElement = function(nums) {
    let minCount = Math.floor(nums.length/2),
        len = nums.length;
    let map = new Map();
    for(let i = 0;i < len;i++) {
        if(map.has(nums[i])) {
            map.set(nums[i], ++map.get(nums[i]));
        }else {
            map.set(nums[i], 1);
        }
    }
    
    let keys = Object.keys(map);
    
    for(let i=0;i<keys.length;i++) {
        if(map.get(keys[i]) > minCount) {
            return keys[i];
        }
    }
    
    return -1;
    
};

console.log(majorityElement([3,2]));

// ② 每次遍历时都记录最大值并且判断
var majorityElement = function(nums) {
    let minCount = nums.length/2,
        max = 0,
        len = nums.length;
    let map = new Map();
    
    for(let i = 0;i < len;i++) {
        map.set(nums[i], map.has(nums[i]) ? map.get(nums[i]) + 1 : 1);
        max = Math.max(max, map.get(nums[i]));
        if(max > minCount) {
            return nums[i];
        }
    }
    
    return -1;
    
};

console.log(majorityElement([2,2,1,1,1,2,2]));